package com.kingwood.algorithm.test;

import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.StringJoiner;

public class HafumanTree {
    static class Node {
        Node lchild;
        Node rchild;
        int weight; // 当前节点的权重；
        int height; // 当前节点所在的高度

        public Node(Node lc, Node rc, int weight, int height) {
            this.lchild = lc;
            this.rchild = rc;
            this.weight = weight;
            this.height  = height;
        }
    }

    public static Node constructHafumanTree(int[] arr) {
        Node root = null;
        if (arr == null || arr.length <= 0) {
            return root;
        }

        // 将哈夫曼树节点进行排序，方便后面筛选出权值最小的两个节点
        // 题目说：当左右节点权值相同时，左子树高度小于等于右子树高度。因此当节点权重相同时，再按照节点子树高度升序
        PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> a.weight != b.weight ? a.weight - b.weight : a.height - b.height);
        int len = arr.length;

        for (int i=0; i<len; i++) {
            Node node = new Node(null, null, arr[i], 0);
            pq.offer(node);
        }

        while (pq.size() > 1) {
            Node lc = pq.poll();
            Node rc = pq.poll();

            int fa_weight = lc.weight + rc.weight;
            int fa_height = rc.height + 1;

            Node fa = new Node(lc, rc, fa_weight, fa_height);
            pq.offer(fa);
        }

        return pq.peek();
    }

    public static void midOrder(Node root, StringJoiner sj) {
        if (root.lchild != null) {
            midOrder(root.lchild, sj);
        }

        sj.add(root.weight + "");

        if (root.rchild != null) {
            midOrder(root.rchild, sj);
        }
    }


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];

        for (int i=0; i<n; i++) {
            arr[i] = scanner.nextInt();
        }

        Node root = constructHafumanTree(arr);

        StringJoiner sj = new StringJoiner(" ");
        if (root != null) {
            midOrder(root, sj);
        }

        System.out.println(sj);
    }
}
